A cryptographic system is available which employs a finite group such as a group formed of the residue classes of integers under multiplication or a group formed of points on an elliptic curve.                In the cryptographic system employing the finite group, it may be judged whether or not h=e·s (when group operation of the finite group is described additively) or h=se (when group operation of the finite group is described multiplicatively) based on elements h and s of the finite group and an integer e in order to verify, for example, the consistency of a ciphertext.        Patent Document 1: JP 2004-201124        Patent Document 2: WO00/39668        Patent Document 3: U.S. Pat. No. 7,110,538        Non-Patent Document 1: R. P. Gallant, R. J. Lambert, S. A. Vanstone, “Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms”, Crypto 2001, LNCS 2139, pp. 190 to 200, 2001        Non-Patent Document 2: “18033-2: Information Technology-Security techniques-Encryption algorithms-Part 2: Asymmetric ciphers”, ISO/IEC 18033-2, 2006        Non-Patent Document 3: R. Cramer, V. Shoup, “Design and Analysis of Practical Public-Key Encryption Schemes secure against Adaptive Chosn Ciphertext Attack” Cryptology ePrint Archive, http://eprint.iacr.org, 2001        Non-Patent Document 4: D. Boneh, X. Boyen, “Efficient Selective-ID Secure Identity Based Encryption Without Random Oracle” EUROCRYPT 2004, LNCS 3027, pp. 223 to 238, 2004        Non-Patent Document 5: X. Boyen, “The BB1 Identity-Based Cryptosystem: A Standard for Encryption and Key Encapsulation”, Submissions for IEEE P1363.3, http://grouper.ieee.org/groups/1363/IBC/submissions/index.html, 2006        Non-Patent Document 6: M. Barbosa, L. Chen, Z. Cheng, M. Chimley, A. Dent, P. Farshim, K. Harrison, J. Malone-Lee, N. P. Smart, F. Vercauteren, “SK-KEM: An Identity-Based KEM”, Submissions for IEEE P1363.3, http://grouper.ieee.org/groups/1363/IBC/submissions/index.html        Non-Patent Document 7: M. Bellare, C. Namprempre, G. Neven, “Security Proofs for Identity-Based Identification and Signature Schemes”, EUROCRYPT 2004, LNCS 3027, 2004        